package com.cdream.basic.algorithm.leetcode.string;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author cdream
 * @date 9/1/21
 */
public class Question165 {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        for(int i = 0;i < Math.max(v1.length,v2.length); i++){
            if(v1.length<=i){
                String e2 =  v2[i];
                int i2 = Integer.parseInt(e2);
                if(i2==0) {
                    continue;
                }
                return -1;
            }
            if(v2.length<=i){
                String e1 =  v1[i];
                int i1 = Integer.parseInt(e1);
                if(i1==0) {
                    continue;
                }
                return 1;
            }
            int i1 = Integer.parseInt(v1[i]);
            int i2 = Integer.parseInt(v2[i]);
            if(i1==i2){
                continue;
            }
            return i1> i2 ? 1: -1;
        }
        return 0;

    }

    public static void main(String[] args) {
        // new Question165().compareVersion("7.5.2.4","7.5.3");
        int[] ints = new Question165().smallestK(new int[]{1, 2, 3,11 ,8,9,4}, 3);
    }

    public int[] smallestK(int[] arr, int k) {
        int[] vec = new int[k];
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        for (int i = 0; i < k; ++i) {
            queue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; ++i) {
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = queue.poll();
        }
        return vec;
    }
}
